package collections;

import util.Tracer;

public class Deque <T>{
		private Object[] items;
		private int head;
		private int tail;
		public Deque(int capacity) {
			items = new Object[capacity + 1];
			head = 0;
			tail = 0;
		}
		
		public void enqueueHead(T t) throws Exception
		{
			int nextHead = (head + items.length - 1) % items.length;
			if(nextHead == tail)
			{
				throw new Exception("overflow head");
			}
			
			items[nextHead] = t;
			head = nextHead;
		}
		
		public void enqueueTail(T t) throws Exception
		{
			int nextTail = (tail + 1) % items.length;
			if(nextTail == head)
			{
				throw new Exception("overflow tail");
			}
			
			items[tail] = t;
			tail = nextTail;
		}
		
		@SuppressWarnings("unchecked")
		public T dequeueHead() throws Exception
		{
			if(head == tail)
				throw new Exception("underflow");
			
			T t = (T)items[head];
			head = (head + 1) % items.length;
			return t;
		}

		@SuppressWarnings("unchecked")
		public T dequeueTail() throws Exception
		{
			if(head == tail)
				throw new Exception("underflow");
			
			int newTail = (tail + items.length - 1) % items.length;
			T t = (T)items[newTail];
			tail = newTail;
			return t;
		}
		
		public static void main(String[] args) throws Exception {
			Deque<Integer> q = new Deque<Integer>(5);
			q.enqueueHead(2);
			q.enqueueHead(1);
			q.enqueueHead(0);
			q.enqueueTail(3);
			q.enqueueTail(4);
			Tracer.trace(q.dequeueTail());
			Tracer.trace(q.dequeueTail());
			Tracer.trace(q.dequeueTail());
			Tracer.trace(q.dequeueTail());
			Tracer.trace(q.dequeueTail());
		}
}
